package Niuke;

import HeuNavigation.Node;
import org.omg.CORBA.PUBLIC_MEMBER;
import sun.misc.Queue;

import javax.management.QueryEval;
import javax.print.attribute.standard.NumberUp;
import javax.transaction.TransactionRequiredException;
import java.lang.reflect.Array;
import java.util.*;

public class Tree {

     public class TreeNode {
     int val = 0;
     TreeNode left = null;
     TreeNode right = null;

     public TreeNode(int val) {
     this.val = val;

     }

     }
    public int TreeDepth(TreeNode root) {
         if (root==null)
             return 0;
        LinkedList<TreeNode> q=new LinkedList<TreeNode>();
        q.add(root);
        int height=0;
        while (!q.isEmpty()){
            int size=q.size();
            while (size>0){
                TreeNode poll = q.poll();
                if (poll.left!=null)
                    q.add(poll.left);
                if (poll.right!=null)
                    q.add(poll.right);
            }
            height++;
        }
        return height;
    }

    public ArrayList<ArrayList<Integer>> Print2(TreeNode pRoot) {
        if (pRoot==null)
            return null;
        LinkedList<TreeNode> q=new LinkedList<TreeNode>();
        q.add(pRoot);
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        int height=0;
        while (!q.isEmpty()){
            ArrayList<Integer> temp=new ArrayList<>();
            int size=q.size();
            while (size>0){
                TreeNode poll = q.poll();
                temp.add(poll.val);
                if (poll.left!=null)
                    q.add(poll.left);
                if (poll.right!=null)
                    q.add(poll.right);
                size--;
            }
            height++;
            if (height%2==0){
                Collections.reverse(temp);
            }
            res.add(temp);
        }
        return res;
    }

    ArrayList<Integer> res=new ArrayList<>();
     int count=0;
    public int KthNode (TreeNode proot, int k) {
        // write code here
        if (proot==null||k<=0) return -1;
        bfs(proot);
        if (count<k) return -1;
        return res.get(k-1);
    }
    public void bfs(TreeNode t){
        if (t==null)
            return;
        bfs(t.left);
        res.add(t.val);
        count++;
        bfs(t.right);
    }

    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
                if (pre.length==0)
                    return null;
                if (pre.length==1)
                    return new TreeNode(pre[0]);
                int rootVal=pre[0];
                TreeNode root=new TreeNode(rootVal);
                int count = 0;
                for (int i=0;i<vin.length;i++){
                    if (vin[i]==rootVal){
                        count=i;
                        break;
                    }
                }
                int[] lPre=Arrays.copyOfRange(pre,1,1+count);
                int[] lVin=Arrays.copyOfRange(vin,0,count);
                int[] rPre=Arrays.copyOfRange(pre,1+count,pre.length);
                int[] rVin=Arrays.copyOfRange(vin,count+1,vin.length);
                root.left=reConstructBinaryTree(lPre,lVin);
                root.right=reConstructBinaryTree(rPre,rVin);
                return root;

    }

    public boolean isSubtree(TreeNode t1,TreeNode t2){
        if (t2==null)
            return true;
        if (t1==null)
            return false;
        if (t1.val!=t2.val)
            return false;
        return isSubtree(t1.left,t2.left)||isSubtree(t1.right,t2.right);
    }
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root1==null||root2==null)
            return false;
        if (isSubtree(root1,root2))
            return true;
        return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
    }

    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if (pRoot==null)
            return null;
        TreeNode t=pRoot.left;
        pRoot.left=Mirror(pRoot.right);
        pRoot.right=Mirror(t);
        return pRoot;
    }

    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot==null) return true;
        LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
        queue.push(pRoot.left);
        queue.push(pRoot.right);
        while (queue.size()>0){
            TreeNode pop = queue.pop();
            TreeNode pop1 = queue.pop();
            if (pop==null&&pop1==null) return true;
            if (pop==null&&pop1!=null) return false;
            if (pop!=null&&pop1==null) return true;
            if (pop.val!=pop1.val) return false;
            queue.push(pop.left);
            queue.push(pop1.right);
            queue.push(pop.right);
            queue.push(pop1.left);
        }
        return true;
    }

    boolean isSame(TreeNode t1,TreeNode t2){
        if (t1==null&&t2==null)
            return true;
        if (t1==null&&t2!=null)
            return false;
        if (t1!=null&&t2==null)
            return false;
        return (t1.val==t2.val)&&(isSame(t1.left,t2.right))&&(isSame(t1.right,t2.left));
    }

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        LinkedList<TreeNode> queue=new LinkedList<>();
        ArrayList<Integer> arr=new ArrayList<>();
        if (root==null)
            return arr;
        queue.add(root);
        while (queue.size()>0){
            TreeNode poll = queue.poll();
            arr.add(poll.val);
            if (poll.left!=null)
                queue.add(poll.left);
            if (poll.right!=null)
                queue.add(poll.right);
        }
        return arr;
    }

    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root==null) return false;
        if (root.left==null&&root.right==null) return root.val==sum;
        return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
    }

    public String convert (String number, int n, int m) {
        // write code here
        HashMap<Integer,Character> map=new HashMap<>();
        for (int i=0;i<=26;i++){
            int c='A'+i;
            char cc=(char)c;
            map.put(10 + i,cc);
        }
        HashMap<Character,Integer> map2=new HashMap<>();
        for (int i=0;i<=26;i++){
            int c='A'+i;
            char cc=(char)c;
            map2.put(cc,10+i);
        }
        if(number==null) return null;
        char[] chars = number.toCharArray();
        int temp=0;
        for (int i=chars.length-1;i>=0;i--){
            int ii=0;
            char tt=chars[i];
            if (Character.isDigit(chars[i])){
                 ii=Integer.parseInt(chars[i]+"");}
            else {
                ii=map2.get(chars[i]);
            }
            temp+=ii*Math.pow(n,chars.length-1-i);
        }
        StringBuffer sb=new StringBuffer();
        while (temp>m){
            int t=temp%m;
            if (t<9) {
                sb.append(temp%m);
            }else {
                sb.append(map.get(t));
            }
            temp=temp/m;
        }
        if (temp<9) {
            sb.append(temp);
        }else {
            sb.append(map.get(temp));
        }
        return sb.reverse().toString();
    }

    public boolean IsBalanced_Solution(TreeNode root) {
            if (root==null)
                return true;
            int llen=len(root.left);
            int rlen=len(root.right);
            int dis=Math.abs(rlen-llen);
            return dis<=1&&IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }
    public int len(TreeNode root){
        if (root==null) return 0;
        int llen=len(root.left);
        int rlen=len(root.right);
        return rlen>=llen?rlen+1:llen+1;
    }

    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        TreeNode t=root;
        while (true){
            int temp=t.val;
            if (p<temp&&q<temp) t=t.left;
            else if(p>temp&&q>temp) t=t.right;
            else{ return temp;}
        }
    }
    public  boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length==0||sequence==null)return false;
        return verfityBST(sequence,0,sequence.length-1);
    }
    public boolean verfityBST(int[] sq,int s,int e){
            if (e<=s)
                return true;
            int index=0;
            for (int i=s;i<e;i++){
                if (sq[index]>sq[e]){
                    index=1;
                    break;
                }
            }
            for (int j=index;j<e;j++){
                if (sq[j]<sq[index])
                    return false;
            }
            return verfityBST(sq,s,index-1)&&verfityBST(sq,index,e-1);
    }


    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> mstack=new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
        if (mstack.isEmpty()){
            mstack.push(node);
        }else {
            if (node<mstack.peek()){
                mstack.push(node);
            }else {
                mstack.push(mstack.peek());
            }
        }
    }

    public void pop() {
        stack1.pop();
        mstack.pop();
    }

    public int top() {
        return stack1.peek();
    }

    public int min() {
        return mstack.peek();
    }

    public String ReverseSentence(String str) {
            if(str==null||str.length()==0) return null;
             String[] s = str.trim().split(" ");
             StringBuilder sb=new StringBuilder();
             for (int i=s.length-1;i>=0;i--){
                 if (s[i].equals(" ")) continue;
                 sb.append(s[i]+" ");
             }
             return sb.toString();
    }

    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res=new ArrayList<>();
        if (pRoot==null) return res;
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.add(pRoot);
        while (!queue.isEmpty()){
            ArrayList<Integer> t=new ArrayList<>();
            int size=queue.size();
            while (size>0){
                TreeNode poll = queue.poll();
                t.add(poll.val);
                if (poll.left!=null) queue.add(poll.left);
                if (poll.right!=null) queue.add(poll.right);
                size--;
            }
            res.add(t);
        }
        return res;
    }

    private ArrayList<ArrayList<Integer>> list=new ArrayList();
    private LinkedList<Integer> record=new LinkedList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        if (root==null) return list;
        dfs(root,expectNumber);
        return list;
    }

    public void dfs(TreeNode root,int num){
        if (root==null) return;
        record.add(root.val);
        if (root.val==num&&root.left==null&&root.right==null)
            list.add(new ArrayList<>(record));

        dfs(root.left,num-root.val);
        dfs(root.right,num-root.val);

        record.remove(record.size()-1);
    }


    int res2=0;

    public void dfs2(TreeNode t,int sum){
        if (t==null) return;
        if (t.val==sum)
            res2++;
        dfs2(t.left,sum-t.val);
        dfs2(t.right,sum-t.val);
    }
    public boolean IsPopOrder(int [] pushA,int [] popA) {
            if (pushA.length==0) return false;
            LinkedList<Integer> s=new LinkedList<>();
            int j=0;
            for (int i=0;i<pushA.length;i++){
                s.push(pushA[i]);
                while (!s.isEmpty()&s.peek()==popA[j]){
                    s.pop();
                    j++;
                }
            }
            return s.isEmpty();

    }

    public int help(TreeNode root,int o1,int o2){
        if (root==null) return -1;
        if (root.val==o1||root.val==o2)
            return root.val;
        int help = help(root.left, o1, o2);
        int help1 = help(root.right, o1, o2);
        if (help==-1) return help1;
        if (help1==-1) return help;
        return root.val;
    }


    TreeNode pre=null;
    TreeNode head=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
            if (pRootOfTree==null)  return null;
            help2(pRootOfTree);
            return head;
    }
    public void help2(TreeNode t){
        help2(t.left);
        if (head==null) head=t;
        if (pre!=null){
            pre.right=t;
            t.left=pre;
        }
        pre=t;
        help2(t.right);
    }


    public static class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }


    static LinkedList<TreeLinkNode> list3=new LinkedList<>();
    public static TreeLinkNode GetNext(TreeLinkNode pNode) {
            TreeLinkNode temp=pNode;
            if(pNode==null) return null;
            while (pNode.next!=null)
                pNode=pNode.next;
            dfs(pNode);
            int index=0;
            for (int i=0;i<list3.size();i++){
                if (list3.get(i)==temp) {
                    index = i;
                    break;
                }
            }
            if (index+1>list3.size()-1) return null;
            return list3.get(index+1);
    }
    public static void dfs(TreeLinkNode node){
        if (node==null) return;
        dfs(node.left);
        list3.add(node);
        dfs(node.right);
    }

    public TreeLinkNode GetNext2(TreeLinkNode pNode) {
            if(pNode==null) return null;
            if (pNode.right!=null){
                TreeLinkNode temp=pNode.right;
                while (temp.left!=null){
                    temp=temp.left;
                }
                return temp;
            }
            while (pNode.next!=null){
                TreeLinkNode t=pNode;
                pNode=pNode.next;
                if (pNode.left==t){
                    return pNode;
                }
            }
            return null;
    }

    //判断是不是搜索二叉树
    public static class ReturnData{
        public boolean isBST;
        public int min;
        public int max;
        public ReturnData(boolean isBST,int min,int max){
            this.isBST=isBST;
            this.min=min;
            this.max=max;
        }
    }
    public static ReturnData process(TreeNode x){
        if (x==null) return null;
        ReturnData leftData = process(x.left);
        ReturnData rightData = process(x.right);

        int min=x.val;
        int max=x.val;

        if (leftData!=null){
            min=Math.min(min,leftData.min);
            max=Math.max(max,leftData.max);
        }

        if (rightData!=null){
            min=Math.min(min,rightData.min);
            max=Math.max(max,rightData.max);
        }
        boolean isbst=true;

        if (leftData!=null&&(!leftData.isBST||leftData.max>=x.val))
            isbst=false;
        if (rightData!=null&&(!rightData.isBST||rightData.min<=x.val))
            isbst=false;

        return new ReturnData(isbst,min,max);
    }
    public boolean isValidBST(TreeNode root) {
        ReturnData process = process(root);
        return process.isBST;
    }


    //判断是不是满二叉树
    public static class data{
        int nodes;
        int height;
        public data(int nodes,int height){
            this.nodes=nodes;
            this.height=height;
        }
    }

    public static data f(TreeNode root){
        if (root==null) return new data(0,0);
        data f = f(root.left);
        data f1 = f(root.right);
        int height=f.height>=f1.height?f.height+1:f1.height+1;
        int nodes=f.nodes+f1.nodes+1;
        return new data(nodes,height);
    }

    public static boolean isFullTree(TreeNode root){
        if (root==null)
            return true;
        data f = f(root);
        return f.nodes==(1<<f.height-1);
    }


    //判断是不是平衡二叉树
    public static class info{
        int height;
        boolean isBlanced;

        public info(int height,boolean isblanced){
            this.height=height;
            this.isBlanced=isblanced;
        }
    }

    public static boolean isBlanced(TreeNode root){
        return process2(root).isBlanced;
    }

    public static info process2(TreeNode root){
        if (root==null) return new info(0,true);
        info info = process2(root.left);
        info info1 = process2(root.right);

        int height=Math.max(info.height,info1.height);
        boolean isbst=info.isBlanced&&info1.isBlanced&&(Math.abs(info.height-info1.height))<2;
        return new info(height,isbst);
    }



    //判断是不是满二叉树
    public static boolean isCBT(TreeNode head){
        if (head==null)
            return true;
        boolean leaf=false;
        TreeNode l=null;
        TreeNode r=null;
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()){
            head=queue.poll();
            l=head.left;
            r=head.right;
            if ((leaf&&(l!=null||r!=null)) || (l==null&&r!=null)) return false;
            if (l!=null)
                queue.add(l);
            if (r!=null)
                queue.add(r);
            if (l==null||r==null)
                leaf=true;
        }
        return true;
    }

    //折纸  凹凸问题
    public static void printAllFolds(int N){
        PrintProcess(1,N,true);
    }
    //i是节点层数，N是一共的层数（折纸的次数），down=true=凹      false=凸
    public static void PrintProcess(int i,int N,boolean down){
        if (i>N)
            return;
        PrintProcess(i+1,N,true);
        System.out.println(down?"凹":"凸");
        PrintProcess(i+1,N,false);
    }

    public static void main(String[] args) {
        TreeLinkNode node=new TreeLinkNode(5);
        node.next=null;
        node.left=null;
        node.right=null;
        Tree.GetNext(node);
    }
}


